\section{Algoritmo Exacto}

\subsection{Presentaci\'on del problema}
Dado un grafo no direccionado con 2 funciones de costo asociadas a cada eje($w_1$ y $w_2$). Se desea encontrar un camino desde un nodo $u$ a otro $v$ que cumpla una cota de costo sobre $w_1$ y que minimize la funci\'on de costo $w_2$. O dicho de otra manera el menor camino desde $u$ a $v$(con el menor $w_2$) tal que $w_1$ cumple una cota $K$.
\\
Se debe plantear un algoritmo que resuelva el problema. Este a priori resulta muy parecido a \emph{Dijkstra} pero con el agregado de una cota que no debe superarse.
\\
\\
\subsection{Resoluci\'on}
Para solucionar este problema proponemos un algoritmo recursivo que utiliza la t\'ecnica de \textit{Backtracking}.
La entrada de dicho algoritmo consiste en el grafo G, donde se corre el algoritmo con los respectivos nodos y ejes y a la vez estos con sus respectivos costos, y los otros datos como $K$ (cota de la sumatoria de los costos $w_1$), \textit{origen} y \textit{destino}, a estos los llamaremos \textit{datos constantes}. Ademas de estos datos, como es recursivo, necesitamos \textit{arrastrar} informaci\'on en cada paso. Para esto agregamos algunas estructuras en la entrada que facilitan esta informaci\'on las cuales llamaremos \textit{datos din\'amicos}:
\begin{itemize}
\item $M$: es una matriz de $n*n$ donde $n$ es la cantidad de nodos de G. En las filas represento a todos los nodos de G y las columnas son la altura en el \'arbol que va formando el algoritmo; Explicaremos m\'as adelante por que la altura no es mayor que $n$. Como en cada paso hace una especie de Dijkstra, en los casilleros guardo una estructura que me dice desde que nodo llego al representado por la fila (si no existe camino al momento pongo NULL), aqu\'i tambi\'en guardo los costos acumulados $w_1$ y $w_2$.
\item $e$: es un nodo. Este nodo es el \"nodo actual\". A partir de este actualizamos las estructuras de M, es decir, vamos llenando la columna correspondiente de M con las adyacenscias de $e$ si es que este camino mejora los costos.
\item $s$: es un entero. Este entero representa la altura en el \'arbol de backtracking y como dijimos antes la columna actual que estoy llenando de $M$. Nos permite conocer rapidamente los costos anteriores para llegar a cada nodo y comparar si estos mejoran.
\item $S$: es un heap de ejes, en este voy agregando los ejes que salen del nodo actual ($e$) y los ordena de menor a mayor de acuerdo a su $w_2$, as\'i facilmente voy eligiendo los ejes que minimizan $w_2$.
\end{itemize}

Al comenzar el algoritmo, $M$ est\'a vacia, $e$ es el \textit{origen}, $s$ es 0 y $S$ esta vacia.
Los \textit{datos constantes} nunca cambian.

En la primera iteraci\'on en el primer \textit{for} lleno la primer columna de $M$ analizando los adyacentes al origen, si $w_1$ es menor que $K$ agrego la informaci\'on correspondiente a la matriz y tambi\'en agrego el eje a $S$.
Luego de la primer iteraci\'on, cada vez que llamo a este \textit{for}, se decide si se actualiza la informaci\'on de cada nodo, es decir, si encuentro un camino con mejor $w_2$ y que sigue cumpliendo la cota $K$, entonces reescribo la posici\'on en $M$ para ese nodo.

Luego entro en un ciclo el cual termina cuando $S$ se queda sin elementos.
Esto ocurre por que el primer paso del ciclo es utilizar el eje de menor $w_2$ y eliminarlo de $S$.
Si un extremo del eje que acabamos de sacar no fue visitado al momento, entonces llamo a la recursi\'on en ese eje, y a partir de este, nuevamente llenamos la matriz $M$ y el heap $S$ con la informaci\'on de los adyacentes de este nodo en un nuevo nivel del arbol de backtracking.

Cuando visitemos todos los nodos, no van a quedar elementos para ingresar en las estructuras, es decir, nuevos ejes para agregar a $S$, es ahi donde el ciclo va continuar hasta agotar los elementos de $S$.

Una vez que el algoritmo agot\'o los ejes por recorrer, reconstruye la soluci\'on mediante la matriz $M$ ya que para cada nodo tengo cual es su antecesor en el mejor camino desde el origen.


\subsection{Pseudoc\'odigo}

\begin{verbatim}
calcularCamino (Grafo G, Matriz M, List$<$Ejes$>$ S,
                 int s, int e, int K, int origen, int destino)
   for G->nodos
      if (existe EJE(e,d) en G)
         if (s==0 y W1 < K) //es la primera iteración?
            -Agrego Información a S
            -Actualizo la Matriz M asignandole de donde vengo
            y el costo de W1 y W2 al momento.
            CONTINUE //sigo a la siguiente iteración
         else
            if (s > 0)
               if (W1 de M hasta ahora + EJE(e,d).W1 no supera K)
                  -Agrego Información a S
                  -Si tengo un nuevo valor para el W2 al momento delnodo d,
                  o mejoro el W2 hasta ahora, agrego la info a M en el paso s
                  CONTINUE
                endif
            endif
         endif
      endif
      -Copio toda la información no actualizada de M a la columna s
   endfor
   Ordeno(S)
   while (S no vacia)
      g = Primero(S) //g es un eje
      EliminoPrimero(S)
      if (existe nodo no visitado en g)
	      g->v //tomo el nodo que todavía no visite de g
	      r = CalcularCamino(G,M,S,s+1,g->v, K, origen, destino)
	  else
	      if (visite todos los nodos y r es no nulo)
	         return r
	      endif
	  endif
   endwhile
   if (recorri todos los nodos y hay camino a destino)
      -reconstruyo camino de origen a destino usando M
      return r
   else
      return NULL
   endif
endCalcularCamino
\end{verbatim}

%\begin{algorithmic}
%\IF{$i$}
%\STATE $S \leftarrow 0$4
%\ENDIF
% G.E ejes
% G.V aristas
% U origen
% V destino
% M matris de resulados parciales.

% # CalcularCamino
% # M matris de reseultados parciales
% # S conjunto de aristas atravesado
% # s step, paso del algoritmo
% # e vertise desde el que se continua la busqueda de caminos
% #	(Dikjstra siempre va a tomar el que cuelgue de la menor arista	)
% # K cota para W1

%\STATE CalcularCamino(M,S,s,e,K)

% 	stk <- sorted stack por w2 del eje

% 	#f arista
%

%	\STATE $stk \leftarrow []$
%	\FOR{ d  in G.V}
%		\IF{$ d != e$  y Existe f in $G.E[e] / f ! in S $}

% 			#agrego la arista a las visitadas.
% 			S = S + f
% 			#desde el nodo e atravesando la arista f
% 			#sigo estando por debajo de la cota K para w1
% 			if  M[s-1][e].w1 + f.w1 < K
% 				d = f.d #d ese l vertice destino del eje f que tiene como origen e
% 				stk.push((w2,d))

% 				#el nodo d era inaccesible o
% 				# desde e tengo mejor distancia
% 				if M[s-1][d].w2 is Null  or M[s-1][e].w2 + f.w2 <  M[s-1][d].w2
% 					M[s][d].w2 = M[s-1][e].w2 + f.w2
% 					M[s][d].w1 = M[s-1][e].w1 + f.w1
%		\ELSE
% 			%para el resto de los nodos los repito los valores anteriores.
% 			\STATE $M[s] \leftarrow M[s-1][d]$
%		\ENDIF
%
%	\ENDFOR
% 	# si llegue al ultimo nodo  y  V esta en el vector retorno el vector de distancias
% 	# donde estara la distancia desde U  a V
% 	if s = |G.V|
% 		if  V in M[s]
% 			return M[s]
% 		else
% 			return vacio

% 	# para los ejes disponibles tomo el de menor w2
% 	# y veo si me lleva a una solucion que llegue hasta V
% 	while (w2,e)  <- stk.pop
% 		if  resultado = CalcularCamino(M,S,s+1,e,K)
% 			return resultado

% 	return vacio
%\end{algorithmic}


\subsection{An\'alisis de complejidad}
Notemos que en peor caso en la primera iteraci\'on cuando partimos desde el origen, este est\'a conectado con todo el resto de los nodos y la conexi\'on cumple con la cota $K$, entonces en el primer \textit{for} hace $O(n)$ asignaciones, comparaciones y operaciones cuando analiza cada eje que sale desde este nodo. Luego ordena la lista de ejes de manera ascendente y esto lo hace en $O(nlog(n))$.
Luego entra en el ciclo por cantidad de ejes en $S$ que acabamos de ordenar llamando a la recursi\'on $n$ veces en la m\'isma altura de backtracking $s+1$.

A la vez en el siguiente paso, por cada recursi\'on llamada, el algoritmo hace lo mismo.

Supongamos que en los siguientes nodos en el \'arbol de backtracking, estos tambi\'en est\'an conectados con todo el resto de los nodos, entonces para cada altura en el \'arbol de backtracking hago $n^s$ llamados a la recursi\'on.

As\'i en el \'ultimo llamado hago $n^n$ llamados.

Entonces la complejidad de este algoritmo es factorial con un grado $n$.

\subsection{Experimentacion}
La experimentación se realizó en base a grafos armados de manera random, los mismos se crearon mediante un script en python que se encuentra dentro de la carpeta ” src” llamado generador.py . se generaron 500 instancias con nodos que se elegían de manera random entre 5 y 200, en base a la cantidad de nodos se generó el grafo completo y se tomó 3/4 de las aristas para que no sea el grafo completo ya que si todos los nodos eran adyacentes entre si y no servía tener todos los casos así. Los valores w1 y w2 de las aristas son números random entre 1 y 100 , el valor de k se genera al final luego de sumar todas los valores de w1 de las aristas saco el promedio y lo multiplico por un valor estimado por distancia entre nodos suponiendo que los nodos están mas próximos si la numeración es próxima.

\includegraphics[scale=0.8]{cacm.jpg} \\
Se puede ver en el grafico que la complejidad del algoritmo es de orden factorial en la cantidad de nodos.

\subsection{C\'odigo de fuente}
\begin{verbatim}
Result* CalcularCamino(Graph* G,Graph* M, list<Edge*>* S,int s,int e,int K,
                       int origen,int destino){
    list<Edge*>* localS = new list<Edge*>;
    *localS = *S;
    Edge *f,*g,*h,*y;
    Result* r = NULL;
    if (existNode(M,e)){
    	return NULL;
    }else{
    }
    M->nodesOrder.push_back(e);
    for (int d=0; d < G->nodes; d++){
        removeEdge(M,d,s);
        f = getEdge(G,e,d,1);
        if (d != e && f != NULL && f->id != -1 &&  !existNode(M,d) ){
            if(s==0 and f->w1 < K){
                g = createEdge(e,f->w1,f->w2);
                localS->push_back(f);
                putEdge(M,d,s,g);
                continue;
            }else{

                if( s > 0 ){
                    g = getEdge(M,e,s-1);
                    if ( g!= NULL && g->w1 + f->w1 < K){
                        localS->push_back(f);
                        h = getEdge(M,d,s-1);
                        if ( h == NULL ||   g->w2 + f->w2 < h->w2 ||
                        ( g->w2+f->w2 == h->w2 &&  g->w1+f->w1 < h->w1 )){
                            y = createEdge(e , g->w1+f->w1, g->w2+f->w2);
                            putEdge(M,d,s,y);
                            continue;
                        }
                    }
                }
            }

        }
        if (s > 0 ){
            g = getEdge(M,d,s-1);
            if (g != NULL){
                putEdge(M,d,s,g);
            }

        }
    }

    localS->sort(compareEdgesByW2);
    int nodesOnCall = M->nodesOrder.size();
    while (localS->size() > 0){
        g = localS->front();
        localS->pop_front();

        if ( !existNode(M,g->u)){
            r = CalcularCamino(G,M,localS,s+1,g->u, K,origen, destino);
        }else{

            if (!existNode(M,g->v)){
            	r = CalcularCamino(G,M,localS,s+1,g->v, K, origen,destino);
            }
        }
        if (NULL != r){
            return r;
        }

        M->nodesOrder.resize(nodesOnCall);
    }
    g = getEdge(M,destino,s);

    if (s == G->nodes-1 && g != NULL){ //reconstruccion del camino.
        r = new Result;
        r->w1 = g->w1;
        r->w2 = g->w2;
        r->k = K;
        int p = destino;
        r->C.push_front(destino);
        while ( p != origen){
            r->C.push_front(g->id);
            g = getEdge(M,g->id,s);
            if (g == NULL){
                break;
            }

            p = g->id;
        }
        r->C.push_front(origen);
        return r;
    }
    return NULL;
}
\end{verbatim}
